﻿// 0915train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <vector>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <deque>

using namespace std;

/*
 按其最高三个分数之和进行降序排名。
 输出降序排名后的选手 ID 序列，条件如下:
1. 一个选手可以有多个射击成绩的分数 且次序不固定
2. 如果一个选手成绩小于三个 则认为选手的所有成绩无效，排名忽略该选手
3. 如果选手的成绩之和相等，则成绩相等的选手按照其 ID 降序排列

输入描述
输入第一行:一个整数 N
表示该场比赛总共进行了N次射击

输入第二行 一个长度为 N 的整数序列
表示参与本次射击的选手 Id

输入第三行是长度为 N 的整数序列
表示参与每次射击的选手对应的成绩

输出描述
符合题设条件的降序排名后的选手 ID 序列

输入
13
3,3,7,4,4,4,4,7,7,3,5,5,5
53,80,68,24,39,76,66,16,100,55,53,80,55
输出
5,3,7,4
 */
class Solution01
{
public:
    Solution01(vector<vector<int>>&num_vec)
    {
        //小于三个,成绩无效
        //成绩之和相等,照其 ID 降序排列
        //ID, score
        for (auto&num_item:num_vec)
        {
            int id = num_item[0], score = num_item[1];
            combine_map[id].push_back(score);
        }

        vector<vector<int>>result;
        for (auto&map_item:combine_map)
        {
            //小于三个,成绩无效
            if (map_item.second.size() < 3) continue;

            //最高三个分数之和进行降序排名
            vector<int>curr_score = map_item.second;
            sort(curr_score.begin(), curr_score.end(), [](int num1, int num2)
                {
                    return num1 > num2;
                });

            int sum = 0;
            for (int i=0; i<3; i++)
            {
                sum += curr_score[i];
            }
            //ID,score
            vector<int>res_item = { map_item.first, sum };
            result.push_back(res_item);
        }

        sort(result.begin(), result.end(), [](vector<int>&vec_1,vector<int>&vec_2)
            {
            //成绩之和相等,照其 ID 降序排列
                if (vec_1[1]==vec_2[1])
                {
                    return vec_1[0] > vec_2[0];
                }
                return vec_1[1] > vec_2[1];
            });

        for (int i=0; i<result.size(); i++)
        {
            cout << result[i][0];
            if (i!=result.size()-1)
            {
                cout << ',';
            }
        }

        //Solution01
    }
private:
    unordered_map<int, vector<int>>combine_map;
};


/*
 输入描述
第1行输入两个整数，学生人数n和科目数量m 0 < n < 100，0 < m < 10

第2行输入m个科目名称，彼此之间用空格隔开，科目名称只由英文字母构成
单个长度不超过10个字符。科目的出现顺字和后续输入的学生成绩一一对应
不会出现重复的科目名称

第3行开始的行，每行包含一个学生的姓名和该生m个科目的成绩空格隔开，学生不会重名
学生姓名只由英文字母构成，长度不超过10个字符。成绩是0~100的整数，依次对应第2行中输入的科目
第n+2行，输入用作排名的科目名称
若科目不存在，则按总分进行排序

输出描述
输出一行，按成绩排序后的学生名字，空格隔开。成绩相同的按照学生姓名字典顺序排序

输入
3 2
yuwen shuxue
fangfang 95 90
xiaohua 88 95
minmin 100 82
shuxue

输出
xiaohua fangfang minmin
 */
class Solution02
{
public:
    vector<int>getTargetIndex(vector<string>& total_kind, unordered_set<string>& target_kind)
    {
        vector<int>target_i;
        if (target_kind.empty())
        {
            return target_i;
        }

        for (int i=0; i<total_kind.size();i++)
        {
	        if (target_kind.count(total_kind[i])>0)
	        {
                target_i.push_back(i);
	        }
        }
        return target_i;
        //getTargetIndex
    }

    Solution02(vector<vector<string>>&origin_vec, vector<string>&total_kind, unordered_set<string>&target_kind)
    {
/*
第n+2行，输入用作排名的科目名称
若科目不存在，则按总分进行排序
*/
        vector<int>target_i = getTargetIndex(total_kind, target_kind);

        vector<pair<string, int>>sort_vec;

        for (auto&single_vec:origin_vec)
        {
            int sum = 0;
            if (target_i.empty())
            {
                for (int i=1; i< single_vec.size(); i++)
                {
                    int score = stoi(single_vec[i]);
                    sum += score;
                }
            }
            else
            {
                for (auto&index:target_i)
                {
                    int score = stoi(single_vec[index + 1]);
                    sum += score;
                }
	            
            }
            sort_vec.push_back(make_pair(single_vec[0], sum));

            //single_vec
        }
        //成绩相同的按照学生姓名字典顺序排序,成绩高的排前面
        sort(sort_vec.begin(), sort_vec.end(), [](pair<string,int>&p_1,pair<string,int>&p_2)
            {
                if (p_1.second==p_2.second)
                {
                    return p_1.first < p_2.first;
                }
                return p_1.second > p_2.second;
            });

        for (int i=0; i<sort_vec.size(); i++)
        {
            cout << sort_vec[i].first;
            if (i!=sort_vec.size()-1)
            {
                cout << ' ';
            }
        }

	    //Solution02
    }
};


/*
 题目描述
火车站附近的货物中转站Q负责将到站货物运往仓库，小明在中转站负责调度2K辆中转车
（K辆干货中转车，K辆湿货中转车）。货物由不同供货商从各地发来，各地的货物是依次进站，
然后小明按照卸货顺序依次装货到中转车上，

一个供货商的货只能装到一辆车上，不能拆装

但是一辆车可以装多家供货商的货；中转车的限载货物量由小明统一制定，
在完成货物中转的前提下，请问中转车的统一限载货物数最小值为多少

输入描述：
第一行 length 表示供货商数量，1 <= length <= 10^4
第二行 goods 表示供货数数组，1 <= goods[i] <= 10^4
第三行 types 表示对应货物类型，types[i] 等于0或者1，0代表干货，1代表湿货
第四行 k 表示单类中转车数量，1 <= k <= goods.length

输出描述：
运行结果输出一个整数，表示中转车统一限载货物数

示例1：
输入
4
3 2 6 3
0 1 1 0
2
输出
6
说明
货物1和货物4为干货，由2辆干货中转车中转，每辆车运输一个货物，限载为3
货物2和货物3为湿货，由2辆湿货中转车中转，每辆车运输一个货物，限载为6
这样中转车统一限载货物数可以设置为6（干货车和湿货车限载最大值），是最小的取值

示例2：
输入
4
3 2 6 8
0 1 1 1
1
输出
16
 */
class Solution03
{
public:
    bool checkVerify(vector<int>&weight_vec, int max_carry)
    {
        
        vector<int>car_vec(car_count_, max_carry);

        int w_size = weight_vec.size();

        
        for (int i= w_size - 1; i>=0; i--)
        {
            bool is_find = false;
            int curr_w = weight_vec[i];
            for (auto&car_w:car_vec)
            {
	            if (car_w>= curr_w)
	            {
                    is_find = true;
                    car_w -= weight_vec[i];
                    break;
	            }
            }
            if (!is_find)
            {
                return false;
            }
        }

        return true;
        //computeCarry
    }

    int getMinWeight(vector<int>&weight_vec)
    {
        if (weight_vec.empty()) return 0;

        int sum = 0;
        for (auto&num:weight_vec)
        {
            sum += num;
        }
        //只有一辆车，全部堆一起
        if (car_count_ == 1) return sum;

        //二分法查找最低载重量
        sort(weight_vec.begin(), weight_vec.end());

        //left必须为最大weight，否则货物装不下
        int w_size = weight_vec.size();
        int left = weight_vec[w_size-1], right = sum + 1;

        int result = 0;
        while (left<right)
        {
            int mid = left + (right - left) / 2;

            if (checkVerify(weight_vec, mid))
            {
	            //缩小载重量
                result = mid;
                right = mid;
            }
            else
            {
                left = mid + 1;
            }

            //while
        }

        return result;
        //getMinWeight
    }

    Solution03(vector<vector<int>>&num_vec, int k)
    {
        car_count_ = k;

        unordered_map<int, vector<int>>combine_map;

        //weight kind
        for (auto&num_item:num_vec)
        {
            int weight = num_item[0], kind = num_item[1];
            combine_map[kind].push_back(weight);
        }

        //两个数组做一次二分法，求出两个数组的最大值
        //0代表干货，1代表湿货
        int max_dry = getMinWeight(combine_map[0]);
        int max_wet = getMinWeight(combine_map[1]);


        cout << max(max_dry, max_wet);
        //Solution03
    }
private:
    int car_count_ = 0;
};


/*
 宝宝和妈妈参加亲子游戏，在一个二维矩阵（N*N）的格子地图上，
 宝宝和妈妈抽签决定各自的位置，
 地图上每个格子有不同的糖果数量，部分格子有障碍物。
游戏规则是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，
路上的所有糖果都可以拿走，不能走障碍物的格子，只能上下左右走。
请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果
（优先考虑最短时间到达的情况下尽可能多拿糖果）。
输入描述
第一行输入为N，N标识二维矩阵的大小
之后N行，每行有N个值，表格矩阵每个位置的值
其中：
- -3：妈妈 -2：宝宝
- -2：宝宝
- -1：障碍
- >=0：糖果数(0表示没有糖果，但是可以走)
输出描述
输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果，行末无多余空格
备注
地图最大50*50

输入
4
3 2 1 -3
1 -1 1 1
1 1 -1 2
-2 1 2 3

输出
9
此地图有两条最短路径可到宝宝位置，都是最短路径6步，但先向下再向左可以拿到9个糖果
 */
class Solution04
{
public:
    void initData(vector<vector<int>>& grid)
    {
        for (int r = 0; r < row_size; r++)
        {
            for (int c = 0; c < col_size; c++)
            {
                //-3：妈妈 -2：宝宝
                if (grid[r][c] == -3)
                {
                    start_row = r;
                    start_col = c;
                }
                if (grid[r][c] == -2)
                {
                    target_row = r;
                    target_col = c;
                }

            }

        }
        //initData
    }

    void setLevel(vector<int>&point_vec, int level)
    {
        stringstream key_sstream;
        key_sstream << point_vec[0] << ',' << point_vec[1];
        string key = key_sstream.str();
        point_level_map[key] = level;
    }

    int getLevel(vector<int>& point_vec)
    {
        stringstream key_sstream;
        key_sstream << point_vec[0] << ',' << point_vec[1];
        string key = key_sstream.str();
        return point_level_map.at(key);
    }

    Solution04(vector<vector<int>>&grid)
    {
        row_size = grid.size();
        col_size = grid[0].size();

        vector<vector<bool>>checked(row_size, vector<bool>(col_size,false));

        dynamic_vec = vector<vector<int>>(row_size, vector<int>(col_size, -1));

        initData(grid);

        int level = 0;

        deque<vector<int>>bfs_queue;
        vector<int>start_point = { start_row,start_col };
        bfs_queue.push_back(start_point);
        //标记已访问
        checked[start_row][start_col] = true;
        dynamic_vec[start_row][start_col] = 0;
        setLevel(start_point, 0);

        bool is_find = false;
        while (!bfs_queue.empty())
        {
            level++;
            int q_size = bfs_queue.size();

            for (int i=0; i<q_size; i++)
            {
                vector<int>top_node = bfs_queue.front();
                bfs_queue.pop_front();

                int prev_val = dynamic_vec[top_node[0]][top_node[1]];
                for (auto&dir_vec:DirectionGrid)
                {
                    int curr_r = top_node[0] + dir_vec[0];
                    int curr_c = top_node[1] + dir_vec[1];

                    if (curr_r==target_row && curr_c==target_col)
                    {
                        dynamic_vec[target_row][target_col] = max(prev_val, dynamic_vec[target_row][target_col]);
                        is_find = true;
                    	break; //退出方向矩阵，不再向前寻找
                    }

                    bool is_curr_r = curr_r >= 0 && curr_r < row_size;
                    bool is_curr_c = curr_c >= 0 && curr_c < col_size;

                    if (is_curr_r&&is_curr_c)
                    {
                        //>=0：糖果数
                        bool is_visited = checked[curr_r][curr_c];
                        bool is_available = grid[curr_r][curr_c] >= 0;

                        //待修改
                        //这个点不在当前这一层里面，才能求dp
                        vector<int>next_point = { curr_r,curr_c };

                        if (!is_visited&&is_available)
                        {
                        	//标记已访问，防止同一个点反复进数组
                            checked[curr_r][curr_c] = true;
                            bfs_queue.push_back(next_point);
                            setLevel(next_point, level);
                        }

                        //这一层刚放进来的，才可以更新
                        if (is_available)
                        {
                            if (getLevel(next_point) == level)
                            {
                                int curr_val = prev_val + grid[curr_r][curr_c];
                                dynamic_vec[curr_r][curr_c] = max(curr_val, dynamic_vec[curr_r][curr_c]);
                            }
                        }

                    }


                    //dir_vec
                }


                //q_size
            }


            if (is_find) break;
            //while (!bfs_queue.empty())
        }

        if (!is_find)
        {
            cout << -1;
            return;
        }

        cout << dynamic_vec[target_row][target_col];

        //Solution04
    }
private:
    int start_row = -1, start_col = -1;
    int target_row = -1, target_col = -1;
    int row_size = 0, col_size = 0;
    unordered_map<string, int>point_level_map;
    vector<vector<int>>dynamic_vec;
    vector<vector<int>>DirectionGrid = { {-1,0},{1,0},{0,-1},{0,1} };
};

int main()
{
	{
        int g_size;
        cin >> g_size;

        vector<vector<int>>grid(g_size, vector<int>(g_size));

        for (int r=0; r< g_size; r++)
        {
            for (int c=0; c<g_size; c++)
            {
                cin >> grid[r][c];
            }
        }

        Solution04 solu(grid);

        return 0;
	}
	{
        int v_size;
        cin >> v_size;

        vector<int>weight_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> weight_vec[i];
        }

        vector<int>kind_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> kind_vec[i];
        }

        vector<vector<int>>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            vector<int>item_v(2);
            item_v[0] = weight_vec[i];
            item_v[1] = kind_vec[i];
            num_vec[i] = item_v;
        }

        int k;
        cin >> k;

        Solution03 solu(num_vec, k);

        return 0;
	}
	{
/*
3 2
yuwen shuxue
fangfang 95 90
xiaohua 88 95
minmin 100 82
shuxue
*/
        int people_size, kind_size;
        cin >> people_size >> kind_size;

        vector<string>total_kind(kind_size);
        for (int i=0; i<kind_size; i++)
        {
            cin >> total_kind[i];
        }

        vector<vector<string>>origin_vec;
        for (int i=0; i<people_size; i++)
        {
            vector<string>people_item(kind_size + 1);
            for (int p=0; p<kind_size+1; p++)
            {
                cin >> people_item[p];
            }
            origin_vec.push_back(people_item);
        }

        cin.ignore();

        unordered_set<string>target_kind;
        string input;
        while (getline(cin,input))
        {
            if (input.empty())break;
            target_kind.insert(input);
        }

        Solution02 solu(origin_vec, total_kind, target_kind);

        return 0;
	}
    //13
    //3,3,7,4,4,4,4,7,7,3,5,5,5
    //53,80,68,24,39,76,66,16,100,55,53,80,55
    int v_size;
    cin >> v_size;
    cin.ignore();
    string id_str;
    getline(cin, id_str);
    stringstream id_sstream(id_str);
    string token;

    vector<int>id_vec;
    while (getline(id_sstream, token, ','))
    {
        id_vec.push_back(stoi(token));
    }

    string score_str;
    getline(cin, score_str);
    stringstream score_sstream(score_str);

    vector<int>score_vec;
    while (getline(score_sstream, token, ','))
    {
        score_vec.push_back(stoi(token));
    }

    vector<vector<int>>num_vec;
    for (int i=0; i<v_size;i++)
    {
        vector<int>num_item(2);
        num_item[0] = id_vec[i];
        num_item[1] = score_vec[i];
        num_vec.push_back(num_item);
    }

    Solution01 solu(num_vec);

    //main
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
